package summer.hot100.v1;

import java.util.LinkedList;
import java.util.List;

public class Solution438 {
    /**
     * https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/645290/438-zhao-dao-zi-fu-chuan-zhong-suo-you-z-nx6b
     *
     * @return
     */
    public List<Integer> findAnagrams(String s, String p) {
        int[] hashP = new int[26];
        for (int i = 0; i < p.length(); i++) {
            hashP[p.charAt(i) - 'a']++;
        }
        int[] hashS = new int[26];
        int left = 0;
        int right = 0;
        List<Integer> res = new LinkedList<>();
        while (right < s.length()) {
            int curRight = s.charAt(right) - 'a';
            hashS[curRight]++;
            while (hashS[curRight] > hashP[curRight]) {
                int curLeft = s.charAt(left) - 'a';
                hashS[curLeft]--;
                left++;
            }
            if (right - left + 1 == p.length()) res.add(left);
            right++;
        }
        return res;
    }
}
